package daily_exercise;

import java.lang.reflect.Constructor;
import java.lang.reflect.Field;
import java.lang.reflect.InvocationTargetException;
import java.time.LocalDate;
import java.time.LocalDateTime;
import java.time.LocalTime;
import java.time.ZoneId;
import java.util.*;

public class Demo6 {


    // 2576. 求出最多标记下标
    public int maxNumOfMarkedIndices(int[] nums) {
        int n = nums.length;
        if (n == 1) return 0;
        Arrays.sort(nums);
        int left = 0, right = n / 2;
        // 数组长度为单数的时候，最多只有 n / 2对，因此 right++ 可以尽可能保证符合题目要求
        if (n % 2 == 1) right++;

        int res = 0;
        while (right < n) {
            if (left < right && nums[left] * 2 <= nums[right]) {
                left++;
                res += 2;
            }
            right++;
        }
        return res;
    }


    // BM83 字符串变形
    public String trans(String s, int n) {
        StringBuilder res = new StringBuilder();
        int left = n - 1, right = n - 1;
        while (left >= 0) {
            while (left >= 0 && s.charAt(left) == ' ') {
                res.append(' ');
                left--;
            }
            if (left < 0) break;
            // 反转单词(left ~ right)
            right = left;
            while (left >= 0 && s.charAt(left) != ' ') left--;
            for (int i = left + 1; i <= right; i++) {
                char ch = s.charAt(i);
                if (ch >= 'a' && ch <= 'z') {
                    res.append((char) (ch - 32));
                } else {
                    res.append((char) (ch + 32));
                }
            }
        }
        return res.toString();
    }


    // 2398. 预算内的最多机器人数目
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int n = chargeTimes.length;
        long[] prevSum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            prevSum[i] = prevSum[i - 1] + runningCosts[i - 1];
        }

        int left = 0, right = 0, res = 0;
        // 维护窗口的最大值
        Deque<Integer> q = new ArrayDeque<>();
        long sum = 0;
        while (right < n) {
            int charge = chargeTimes[right];
            // 入窗口
            if (q.isEmpty()) {
                q.addFirst(charge);
            } else {
                if (charge > q.peekFirst()) {
                    q.clear();
                    q.addFirst(charge);
                } else {
                    while (charge > q.peekLast()) {
                        q.removeLast();
                    }
                    q.addLast(charge);
                }
            }
            // 出窗口
            while (!q.isEmpty() && q.peekFirst() + (right - left + 1) * (prevSum[right + 1] - prevSum[left]) > budget) {
                if (chargeTimes[left++] == q.peekFirst()) q.removeFirst();
            }
            res = Math.max(res, right - left + 1);
            right++;
        }
        return res;
    }


    // 2390. 从字符串中移除星号
    public String removeStars(String s) {
        StringBuilder res = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (ch != '*') {
                res.append(ch);
            } else {
                res.deleteCharAt(res.length() - 1);
            }
        }
        return res.toString();
    }


    // 2848. 与车相交的点
    public int numberOfPoints(List<List<Integer>> nums) {
        nums.sort((a, b) -> a.get(0) - b.get(0));
        int startIndex = 0, endTime = nums.get(0).get(1), cur = 1;
        int n = nums.size();

        int res = 0;
        while (cur < n) {
            if (endTime < nums.get(cur).get(0)) {
                res += endTime - nums.get(startIndex).get(0) + 1;
                startIndex = cur;
                endTime = nums.get(cur).get(1);
            } else {
                endTime = Math.max(endTime, nums.get(cur).get(1));
            }
            cur++;
        }
        res += endTime - nums.get(startIndex).get(0) + 1;
        return res;
    }


    // 1184. 公交站间的距离
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int n = distance.length;
        int sum = 0;
        for (int x : distance) sum += x;

        if (start > destination) {
            int tmp = start;
            start = destination;
            destination = tmp;
        }
        int tmp = 0;
        for (int i = start; i < destination; i++) {
            tmp += distance[i];
        }
        return Math.min(tmp, sum - tmp);
    }


    // 2332. 坐上公交的最晚时间
    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        int n = buses.length, m = passengers.length;
        Arrays.sort(buses);
        Arrays.sort(passengers);

        int count = 0;  // 记录此趟公交车载了多少乘客
        int i = 0;      // 记录公交车的序号
        int j = 0;      // 记录乘客的序号
        while (i < n && j < m) {
            count = 0;
            while (j < m && count < capacity && passengers[j] <= buses[i]) {
                j++;
                count++;
            }
            i++;
        }

        // 1. 前面的公交车已载满了所有乘客
        if (j == m && i <= n - 1) return buses[n - 1];
        // 2. 最后一趟公交车未载满乘客
        if (count < capacity) {
            int res = buses[n - 1];
            j--;
            while (j >= 0 && res == passengers[j]) {
                res--;
                j--;
            }
            return res;
        }
        // 3. 最后一趟公交车已载满乘客
        int res = passengers[j - 1] - 1;
        j -= 2;
        while (j >= 0 && res == passengers[j]) {
            res--;
            j--;
        }
        return res;
    }


    // 2414. 最长的字母序连续子字符串的长度
    public int longestContinuousSubstring(String s) {
        int n = s.length();
        int a = 1, b = 0;

        int res = 1;
        for (int i = 1; i < n; i++) {
            b = 1;
            if (s.charAt(i) == s.charAt(i - 1) + 1) {
                b = a + 1;
                res = Math.max(res, b);
            }
            a = b;
        }
        return res;
    }


    // 2374. 边积分最高的节点
    public int edgeScore(int[] edges) {
        int n = edges.length;
        long[] sum = new long[n];

        int res = -1;
        long max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int to = edges[i];
            sum[to] += i;

            if (sum[to] > max || (sum[to] == max && to < res)) {
                res = to;
                max = sum[to];
            }
        }

        return res;
    }


    // 997. 找到小镇的法官
    public int findJudge(int n, int[][] trust) {
        // 该编号的人是否相信他人
        boolean[] flag = new boolean[n + 1];
        // 该编号的人是否被他人相信
        int[] isTrusted = new int[n + 1];
        for (int[] arr : trust) {
            flag[arr[0]] = true;
            isTrusted[arr[1]]++;
        }

        boolean isExist = false;
        int res = -1;
        for (int i = 1; i <= n; i++) {
            if (!flag[i] && isTrusted[i] == n - 1) {
                // if (isExist) return -1;
                isExist = true;
                res = i;
            }
        }
        return res;
    }


    // 1014. 最佳观光组合
    public int maxScoreSightseeingPair(int[] values) {
        // values[i] + i 为一组, values[j] - j 为一组
        int max = 0;
        int n = values.length;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (values[i] - i + max > res) {
                res = values[i] - i + max;
            }
            // 更新 values[i] + i 的最大值
            max = Math.max(values[i] + i, max);
        }
        return res;
    }


    // 2207. 字符串中最多数目的子序列
    public long maximumSubsequenceCount(String text, String pattern) {
        // 贪心: (1) 将pattern[0] 插入到 text 的第一个位置
        //       (2) 将pattern[1] 插入到 text 的最后一个位置
        int a = pattern.charAt(0), b = pattern.charAt(1);
        int first = 1;
        long res = 0;
        for (char ch : text.toCharArray()) {
            if (ch == b) {
                res += first;
            }
            if (ch == a) {
                first++;
            }
        }

        int second = 1, n = text.length();
        long tmp = 0;
        for (int i = n - 1; i >= 0; i--) {
            char ch = text.charAt(i);
            if (ch == a) {
                tmp += second;
            }
            if (ch == b) {
                second++;
            }
        }

        return Math.max(res, tmp);
    }


    // 2306. 公司命名
    public long distinctNames(String[] ideas) {
        // 1. 将公司名字按首字母分类，存储其后缀
        Set<String>[] hashs = new Set[26];
        Arrays.setAll(hashs, i -> new HashSet<>());
        for (String s : ideas) {
            String sub = "";
            if (s.length() > 1) {
                sub = s.substring(1, s.length());
            }
            hashs[s.charAt(0) - 'a'].add(sub);
        }

        // 2. 两两进行枚举
        long res = 0;
        for (int i = 0; i < 25; i++) {
            for (int j = i + 1; j < 26; j++) {
                Set<String> longer = hashs[i], shorter = hashs[j];
                if (hashs[i].size() < hashs[j].size()) {
                    longer = hashs[j];
                    shorter = hashs[i];
                }

                int common = 0;
                for (String s : shorter) {
                    if (longer.contains(s)) {
                        common++;
                    }
                }
                res += (long) (longer.size() - common) * (shorter.size() - common) * 2;
            }
        }
        return res;
    }


    // 2535. 数组元素和与数字和的绝对差
    public int differenceOfSum(int[] nums) {
        int eleSum = 0, numSum = 0;
        for (int x : nums) {
            eleSum += x;
            while (x > 0) {
                numSum += x % 10;
                x /= 10;
            }
        }
        return Math.abs(eleSum - numSum);
    }


    // 2516. 每种字符至少取 K 个
    public int takeCharacters(String s, int k) {
        int n = s.length();
        int[] counts = new int[3];
        for (char ch : s.toCharArray()) {
            counts[ch - 'a']++;
        }
        for (int i = 0; i < 3; i++) {
            if (counts[i] < k) return -1;
        }

        // 滑动窗口，使得窗口内'a','b','c'的数目最多分别满足下列数量
        // 找出最大的窗口
        for (int i = 0; i < 3; i++) {
            counts[i] -= k;
        }
        int[] flags = new int[3];
        int left = 0, right = 0;
        int res = 0;
        while (right < n) {
            char ch = s.charAt(right);
            flags[ch - 'a']++;
            while (left <= right && flags[ch - 'a'] > counts[ch - 'a']) {
                flags[s.charAt(left) - 'a']--;
                left++;
            }
            res = Math.max(res, right - left + 1);
            right++;
        }
        return n - res;
    }


    // 2073. 买票需要的时间
    public int timeRequiredToBuy(int[] tickets, int k) {
        int n = tickets.length;
        // 存储 0 ~ n - 1 下标的人需要的买票时间
        int[] res = new int[n];
        // left 记录当前下标左边有多少人继续买票
        int[] left = new int[n];
        for (int i = 0; i < n; i++) left[i] = i;
        int count = n;

        while (count > 0) {
            for (int i = 0; i < n; i++) {
                if (tickets[i] > 0) {
                    // 等待前面买票的人 + 自己买票 1 秒
                    res[i] += left[i] + 1;
                    // 下次买票需要等待的人数
                    left[i] = count - 1;
                    if (--tickets[i] == 0) count--;
                }
            }
        }

        return res[k];
    }


    // 1845. 座位预约管理系统
    class SeatManager {
        PriorityQueue<Integer> pq;

        public SeatManager(int n) {
            pq = new PriorityQueue<>();
            for (int i = 1; i <= n; i++) {
                pq.add(i);
            }
        }

        public int reserve() {
            return pq.poll();
        }

        public void unreserve(int seatNumber) {
            pq.add(seatNumber);
        }
    }




    // 983. 最低票价
    boolean[] isTravel;
    int[] memo;
    public int mincostTickets(int[] days, int[] costs) {
        int n = days.length;
        isTravel = new boolean[366];
        for (int x : days) {
            isTravel[x] = true;
        }
        memo = new int[days[n - 1] + 1];
        return dfs(days[n - 1], costs);
    }
    // 求第 1 天到第 cur 天旅行所需的最低消费
    private int dfs(int cur, int[] costs) {
        // 不合法，结果为 0
        if (cur <= 0) return 0;
        // 存在记忆化搜索结果中
        if (memo[cur] != 0) {
            return memo[cur];
        }
        // 当天不在旅行计划中，求 1 ~ cur - 1 天的消费
        if (!isTravel[cur]) {
            return dfs(cur - 1, costs);
        }
        memo[cur] = Math.min(dfs(cur - 1, costs) + costs[0], Math.min(dfs(cur - 7, costs) +  costs[1], dfs(cur - 30, costs) + costs[2]));
        return memo[cur];
    }




    // 2187. 完成旅途的最少时间
    public long minimumTime(int[] time, int totalTrips) {
        int max = 0;
        for (int x : time) {
            if (x > max) max = x;
        }

        long left = 1, right = (long)totalTrips * max, mid = 0;
        // 二分查找左边界
        while (left < right) {
            mid = left + (right - left) / 2;
            if (check(time, mid, totalTrips)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    private boolean check(int[] time, long x, int totalTrips) {
        long count = 0, n = time.length;
        for (int i = 0; i < n; i++) {
            count += x / time[i];
        }
        return count >= totalTrips;
    }



    // 134. 加油站
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            if (gas[i] - cost[i] < 0) continue;

            int sum = 0, step = 0;
            for (int j = i; step < n; step++) {
                sum += gas[j] - cost[j];
                if (sum < 0) break;
                j = (j + 1) % n;
            }
            if (step == n) return i;
            i += step;      // 以 i ~ i + setp 位置为起点一定不符合要求
        }
        return -1;
    }




    // 871. 最低加油次数
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        if (startFuel >= target) return 0;
        // 将加油站距离出发点的距离由近到远排序
        Arrays.sort(stations, (a, b) -> a[0] - b[0]);
        int n = stations.length;
        int pos = 0;    // 记录经过的加油站下标
        int cur = startFuel;
        // 统计所有已经过加油站的补充油量(大根堆)
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int count = 0;
        while (pos < n && (!pq.isEmpty() || cur >= stations[pos][0])) {
            if (cur >= stations[pos][0]) {
                pq.offer(stations[pos++][1]);
            } else {
                if (pq.isEmpty()) break;
                cur += pq.poll();
                count++;
            }
        }
        // 到达不了途中的某一加油站
        if (pos < n) return -1;
        // 已经过途中所有加油站，根据需要加油(每次在油量最大的加油站加油)
        while (cur < target && !pq.isEmpty()) {
            cur += pq.poll();
            count++;
        }
        return cur >= target ? count : -1;
    }




    // 1436. 旅行终点站
    public String destCity(List<List<String>> paths) {
        Set<String> hash = new HashSet<>();     // 统计有出度的节点
        Set<String> res = new HashSet<>();      // 统计可能为结果的节点
        for (List<String> path : paths) {
            // res 的出度为 0
            String s1 = path.get(0), s2 = path.get(1);
            hash.add(s1);
            if (res.contains(s1)) {
                res.remove(s1);
            }
            if (!hash.contains(s2)) {
                res.add(s2);
            }
        }
        return res.toArray(new String[0])[0];
    }



    // 3162. 优质数对的总数 I
    public int numberOfPairs(int[] nums1, int[] nums2, int k) {
        int n = nums1.length, m = nums2.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (nums1[i] % (k * nums2[j]) == 0) res++;
            }
        }
        return res;
    }



    // 3164. 优质数对的总数 II
    public long numberOfPairs2(int[] nums1, int[] nums2, int k) {
        int n = nums1.length, m = nums2.length;
        Map<Integer,Integer> hash1 = new HashMap<>(), hash2 = new HashMap<>();
        int max = 0;
        // 1. 统计 nums1 各个数字出现的次数并找到最大值
        for (int x : nums1) {
            if (x % k != 0) continue;
            x /= k;
            hash1.put(x, hash1.getOrDefault(x, 0) + 1);
            if (x > max) max = x;
        }
        // 2. 统计 nums2 各个数字出现的次数
        for (int x : nums2) {
            hash2.put(x, hash2.getOrDefault(x, 0) + 1);
        }
        // 3. 枚举 hash2 中每个数的倍数是否在 hash1 中出现，且不超过 max
        long res = 0;
        for (int x : hash2.keySet()) {
            int times = 1;
            while (x * times <= max) {
                if (hash1.containsKey(x * times)) {
                    res += (long)hash1.get(x * times) * hash2.get(x);
                }
                times++;
            }
        }
        return res;
    }
    
    
    
    
    // 1884. 鸡蛋掉落-两枚鸡蛋
    private int[] memo2;
    public int twoEggDrop(int n) {
        memo2 = new int[n + 1];
        Arrays.fill(memo2, -1);
        return dfs(n);
    }
    private int dfs(int n) {
        if (n == 0) return 0;
        if (memo2[n] != -1) return memo2[n];

        int res = Integer.MAX_VALUE;
        // 枚举第一枚鸡蛋扔下的楼层高度
        for (int i = 1; i <= n; i++) {
            // 如果第一个鸡蛋碎了，则最大可能试 1 ~ i 总共 i 次
            // 第一个鸡蛋没碎 -> 从 i + 1 层到 n 层总共 n - i 层寻找最小操作次数 dfs(n - i) + 1 （第一次操作没碎）
            res = Math.min(res, Math.max(i, dfs(n - i) + 1));
        }
        // 存储之前计算的结果
        return memo2[n] = res;
    }



    // 3158. 求出出现两次数字的 XOR 值
    public int duplicateNumbersXOR(int[] nums) {
        boolean[] exists = new boolean[51];
        int res = 0;
        for (int x : nums) {
            if (exists[x]) {
                res ^= x;
            }
            exists[x] = true;
        }
        return res;
    }




    // 3194. 最小元素和最大元素的最小平均值
    public double minimumAverage(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int left = 0, right = n - 1;

        double res = 0x3f3f3f3f;
        while (left < right) {
            double avg = (nums[left] + nums[right]) * 1.0 / 2;
            if (avg < res) {
                res = avg;
            }
            left++; right--;
        }
        return res;
    }




    // 3191. 使二进制数组全部等于 1 的最少操作次数 I
    public int minOperations(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                if (n - i < 3) return -1;

                for (int j = i; j < i + 3; j++) {
                    nums[j] = 1 - nums[j];
                }
                res++;
            }
        }
        return res;
    }



    // 3192. 使二进制数组全部等于 1 的最少操作次数 II
    public int minOperations2(int[] nums) {
        // 记录需要翻转的次数
        int res = 0;
        for (int x : nums) {
            if (x == 1 && res % 2 == 0) continue;
            if (x == 0 && res % 2 == 1) continue;

            res++;
        }
        return res;
    }



    // 908. 最小差值 I
    public int smallestRangeI(int[] nums, int k) {
        int min = 0x3f3f3f3f, max = -0x3f3f3f3f;
        for (int x : nums) {
            if (x > max) max = x;
            if (x < min) min = x;
        }

        return max - min <= 2 * k ? 0 : max - min - 2 * k;
    }



    // 910. 最小差值 II
    public int smallestRangeII(int[] nums, int k) {
        // 大的变小，小的变大
        int n = nums.length;
        if (n == 1) return 0;
        Arrays.sort(nums);
        int res = nums[n - 1] - nums[0];    // 对应把数全部变大或变小
        // 0 ~ i 的数全部变大, i + 1 ~ n - 1的数全部变小
        for (int i = 0; i < n - 1; i++) {
            int max = Math.max(nums[i] + k, nums[n - 1] - k);
            int min = Math.min(nums[0] + k, nums[i + 1] - k);
            res = Math.min(res, max - min);
        }
        return res;
    }



    // 3184. 构成整天的下标对数目 I
    public int countCompleteDayPairs(int[] hours) {
        // 统计各个数 %24 后的余数，数量
        int[] modCounts = new int[24];
        int res = 0;
        for (int x : hours) {
            if (x % 24 == 0) {
                res += modCounts[0];
            } else {
                res += modCounts[24 - x % 24];
            }
            modCounts[x % 24]++;
        }
        return res;
    }



    // 3185. 构成整天的下标对数目 II
    public long countCompleteDayPairs2(int[] hours) {
        int[] modCounts = new int[24];
        long res = 0;
        for (int x : hours) {
            if (x % 24 == 0) {
                res += modCounts[0];
            } else {
                res += modCounts[24 - x % 24];
            }
            modCounts[x % 24]++;
        }
        return res;
    }



    // 3175. 找到连续赢 K 场比赛的第一位玩家
    public int findWinningPlayer(int[] skills, int k) {
        LinkedList<Integer> q = new LinkedList<>();
        q.addFirst(0);
        int n = skills.length;
        int count = 0;
        for (int i = 1; i < n; i++) {
            if (skills[q.peekFirst()] > skills[i]) {
                if (++count == k) return q.peekFirst();
                q.addLast(i);
            } else {
                count = 1;
                q.addLast(q.removeFirst());
                q.addFirst(i);
                if (k == 1) break;
            }
        }
        return q.peekFirst();
    }



    // 684. 冗余连接
    private int[] father;
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        // 初始化并查集
        father = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            father[i] = i;
        }

        for (int[] e : edges) {
            int x = e[0], y = e[1];
            if (isSame(x, y)) return e;
            join(x, y);
        }
        return null;
    }
    private int find(int x) {
        if (father[x] == x) return x;
        return find(father[x]);
    }
    private void join(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        father[x] = y;
    }
    private boolean isSame(int x, int y) {
        return find(x) == find(y);
    }



    // 685. 冗余连接 II
//    private int[] father;
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        // 1. 并查集初始化
        father =  new int[n + 1];
        for (int i = 1; i <= n; i++) {
            father[i] = i;
        }
        // 2. 统计各边的入度
        int[] inDegree = new int[n + 1];
        for (int[] e : edges) {
            inDegree[e[1]]++;
        }
        // 3. 若存在入度为 2 的节点，则相连的边加入集合
        List<Integer> twoDegree = new ArrayList<>();
        for (int i = n - 1; i >= 0; i--) {
            int node = edges[i][1];
            if (inDegree[node] == 2) twoDegree.add(i);
        }
        // 若集合不为空，则删除其中一条边
        if (!twoDegree.isEmpty()) {
            if (isTreeAfterRemoveEdge(edges, twoDegree.get(0))) {
                return edges[twoDegree.get(0)];
            }
            return edges[twoDegree.get(1)];
        }

        // 5. 所有节点的入度都为 1，删除构成环的边
        for (int i = 0; i < n; i++) {
            int[] e = edges[i];
            int x = e[0], y = e[1];
            if (isSame(x, y)) return e;
            join(x, y);
        }
        return new int[0];
    }
//    private int find(int x) {
//        if (father[x] == x) return x;
//        return father[x] = find(father[x]);
//    }
//    private void join(int x, int y) {
//        x = find(x);
//        y = find(y);
//        if (x == y) return;
//        father[x] = y;
//    }
//    private boolean isSame(int x, int y) {
//        return find(x) == find(y);
//    }
    private boolean isTreeAfterRemoveEdge(int[][] edges, int index) {
        for (int i = 0; i < edges.length; i++) {
            if (i == index) continue;
            int[] e = edges[i];
            int x = e[0], y = e[1];
            if (isSame(x, y)) return false;
            join(x, y);
        }
        return true;
    }
}


